package org.example.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 */
public class Code131 {
    List<String> path=new ArrayList<>();
    List<List<String>> res=new ArrayList<>();
    public List<List<String>> partition(String s) {
        res.clear();  // 清空之前的结果
        path.clear(); // 清空之前的路径
        backtracking(s,0);
        return res;
    }

    private void backtracking(String s, int startIndex) {
        if(startIndex==s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<s.length();i++){
            if(isPair(s,startIndex,i)){
                path.add(s.substring(startIndex,i+1));
                backtracking(s,i+1);
                path.remove(path.size()-1);
            }
        }
    }

    private boolean isPair(String s, int start, int end) {
        while (start <= end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Code131 solution = new Code131();

        // 测试用例1
        String s1 = "aab";
        List<List<String>> result1 = solution.partition(s1);
        System.out.println("输入: \"" + s1 + "\"");
        System.out.println("输出: " + result1);
        System.out.println();

        // 测试用例2
        String s2 = "a";
        List<List<String>> result2 = solution.partition(s2);
        System.out.println("输入: \"" + s2 + "\"");
        System.out.println("输出: " + result2);
        System.out.println();

        // 测试用例3
        String s3 = "abcba";
        List<List<String>> result3 = solution.partition(s3);
        System.out.println("输入: \"" + s3 + "\"");
        System.out.println("输出: " + result3);
    }
}
